1. Field of the Invention
The present invention relates to the field of memory management. More particularly, the present invention relates to methods and apparatus for replacing the contents of a memory.
2. Background
The terms memory and storage have been used interchangeably. Of the two terms, storage is used more commonly. Programs and data must be in main storage in order to be run or referenced directly. A random access memory (RAM) is typically used for the main storage. Programs or data not needed immediately may be kept in a secondary storage until needed and then brought into the main storage for execution or reference. Secondary storage provides large, inexpensive storage for the abundance of programs and data that must be kept readily available for processing. Some typical examples of secondary storage include disks, tapes and drums. Main storage is typically accessible much faster than secondary storage.
Referring to FIG. 1, computer systems typically have several levels of storage, requiring multiple data transfers between the various levels. This data transfer consumes system resources such as central processing unit (CPU) time that could otherwise be put to productive use. An improvement in system resource utilization is made possible by using a cache 1. A cache 1 is a high-speed storage that is much faster than the main storage 2. Cache 1 is typically extremely expensive compared with main storage 2 and therefore only relatively small caches are used.
Cache 1 requires one additional level of data transfer on the system. Programs and data in the main storage 2 are transferred to the high-speed cache 1 before being executed. When the CPU requests data that is not already in cache 1 or main storage 2, a block containing the requested data is read from secondary storage 3. The data is retained in the cache 1 with the hope that subsequently requested data will already be in the cache 1. Successful cache 1 utilization requires that the overhead involved in transferring programs between storage layers 1, 2 and 3 is smaller than the performance increase obtained by the faster execution possible in the cache 1.
The performance of a system utilizing a cache may be measured according to its hit ratio. A xe2x80x9chitxe2x80x9d is defined as a request for data, which is already in cache 1. A xe2x80x9cmissxe2x80x9d is defined as a request for data that is not already in cache 1. The hit ratio is defined as the number of hits divided by the total number of cache accesses. Due to the performance advantages of using a cache 1, data already in cache 1 is kept there as long as possible, thus maximizing the hit ratio. However, data in cache 1 must be replaced when the cache 1 is full and additional data not already in cache 1 is requested.
One typical method of determining which data in cache 1 to replace is xe2x80x9cfirst-in-first-outxe2x80x9d (FIFO). Each data set, or frame, is time-stamped when it is placed in cache 1. When a frame needs to be replaced, the frame with the oldest time-stamp is chosen. Unfortunately, the FIFO method is likely to replace heavily used frames because the reason a frame may be in cache 1 for a long period may be because it is in constant use.
Another typical replacement method is xe2x80x9cleast-recently-usedxe2x80x9d (LRU). This method selects the frame for replacement that has not been used for the longest time. LRU assumes the recent past is a good indicator of the near future. It is typically implemented with timers or counters that determine the amount of time elapsed since a frame was accessed.
LRU timer implementations require complicated timing circuitry. Moreover, LRU timer implementations require a time stamp update every time a page is accessed. These factors can require substantial overhead, both in terms of timing and memory.
LRU counter implementations typically employ linear counters to indicate the age in cache 1 of the associated cache data. With every cache 1 access, a time tag is incremented if the associated frame is not the frame requested. Since the counters are linear, a large number of bits are required to represent the age in cache 1 of the associated frame. The advantages of using a time tag lessen when the number of accesses between replacements typically exceeds the maximum number represented by the time tag. Past this point, there is no way to distinguish the age of the data. Consequently, LRU cache replacement is often not implemented in current systems. A need exists in the prior art for a cache replacement method and apparatus that approximates LRU and requires minimal overhead.
A method and apparatus for efficiently replacing the contents of a memory is disclosed. The memory comprises a plurality of data blocks and associated time tags. Each time tag approximates the age in the memory for the associated block. A memory access count is updated with every memory access. The time tags for all memory blocks are updated to reflect their age in memory based upon the memory access count. When a memory miss occurs, the block with a time tag value representing the highest residence time in memory with respect to other time tags is replaced with the new block and the new block is assigned a time tag value representing the least amount of time in memory. When a memory hit occurs, the requested block is assigned a time tag value representing the least amount of time in memory.